#include<iostream>
#include<cstdio>
using namespace std;
int n,m,q;
long long a[200010];
long long gapS[200010],d[200010];
long long ans[200010];
bool tag[200010];

struct Query
{
	int l,r;
	int id;
	Query(){}
	Query(int tl,int tr,int tid)
	{
		l=tl;
		r=tr;
		id=tid;
	}
}qrList[200010],lqrList[200010],rqrList[200010],mqrList[200010];
int qrtot;

const int B=500;
long long tans[200010];
long long lf[200010],rf[200010];

void Solve1(int nl,int nr,int ql,int qr,int m)
{
	if(ql>qr) return;
	if(nl==nr)
	{
		for(int i=ql;i<=qr;i++) ans[qrList[i].id]+=max(a[nl],0ll);
		return;
	}
	int mid=(nl+nr)/2;
	int lqrtot=0,rqrtot=0,mqrtot=0;
	for(int i=ql;i<=qr;i++)
	{
		if(qrList[i].r<=mid) lqrList[++lqrtot]=qrList[i];
		else if(qrList[i].l>=mid+1) rqrList[++rqrtot]=qrList[i];
		else mqrList[++mqrtot]=qrList[i];
	}
	// cerr<<"a: ";for(int i=nl;i<=nr;i++) cerr<<a[i]<<' ';cerr<<'\n';
	// cerr<<"qr:\n";for(int i=ql;i<=qr;i++) cerr<<qrList[i].id<<' '<<qrList[i].l<<' '<<qrList[i].r<<'\n';
	// cerr<<"qrend"<<'\n';
	// cerr<<"qrtot: "<<lqrtot<<' '<<rqrtot<<' '<<mqrtot<<'\n';
	for(int i=mid-m+2;i<=mid+1;i++)
	{
		int L=i,R=i+m-2;
		// cerr<<"Solve: "<<nl<<' '<<nr<<' '<<mid<<' '<<L<<' '<<R<<'\n';

		if(L>=nl)
		{
			lf[L]=0;
			for(int j=L-1;j>=nl;j--)
			{
				lf[j]=lf[j+1];
				if(j+m<=L-1) lf[j]=max(lf[j],lf[j+m]+a[j]);
				else lf[j]=max(lf[j],a[j]);
			}
		}
		if(R<=nr)
		{
			rf[R]=0;
			for(int j=R+1;j<=nr;j++)
			{
				rf[j]=rf[j-1];
				if(j-m>=R+1) rf[j]=max(rf[j],rf[j-m]+a[j]);
				else rf[j]=max(rf[j],a[j]);
			}
		}
		for(int j=1;j<=mqrtot;j++)
		{
			long long val=0;
			if(mqrList[j].l<=L) val+=lf[mqrList[j].l];
			if(mqrList[j].r>=R) val+=rf[mqrList[j].r];
			tans[mqrList[j].id]=max(tans[mqrList[j].id],val);
			// cerr<<"cg: "<<mqrList[j].id<<' '<<mqrList[j].l<<' '<<mqrList[j].r<<' '<<lf[mqrList[j].l]<<' '<<rf[mqrList[j].r]<<'\n';
		}
	}
	// for(int i=1;i<=mqrtot;i++) ans[mqrList[i].id]+=tans[mqrList[i].id]/*,cerr<<"tans: "<<tans[mqrList[i].id]<<'\n'*/;
	for(int i=1;i<=lqrtot;i++) qrList[ql+i-1]=lqrList[i];
	for(int i=1;i<=rqrtot;i++) qrList[ql+lqrtot+i-1]=rqrList[i];
	Solve1(nl,mid,ql,ql+lqrtot-1,m);
	Solve1(mid+1,nr,ql+lqrtot,ql+lqrtot+rqrtot-1,m);
}
int rval[200010];
long long la[200010],ra[200010],ta[200010];
int aid[200010];
int L[100010],R[100010],blkcnt;
void Solve2(int nl,int nr,int ql,int qr,int m)
{
	if(ql>qr) return;
	int mid=(1+m)/2;

	blkcnt=0;
	L[++blkcnt]=nl;
	R[blkcnt]=min(nl+mid-1,nr);
	for(int i=nl+mid;i<=nr;i+=m)
	{
		L[++blkcnt]=i;
		R[blkcnt]=min(i+m-1,nr);
	}
	for(int i=1;i<=blkcnt;i++)
	{
		lf[L[i]]=0;
		for(int j=L[i]-1;j>=nl;j--)
		{
			lf[j]=lf[j+1];
			if(j+m<=L[i]-1) lf[j]=max(lf[j],lf[j+m]+a[j]);
			else lf[j]=max(lf[j],a[j]);
		}
		rf[R[i]]=0;
		for(int j=R[i]+1;j<=nr;j++)
		{
			rf[j]=rf[j-1];
			if(j-m>=R[i]+1) rf[j]=max(rf[j],rf[j-m]+a[j]);
			else rf[j]=max(rf[j],a[j]);
		}
		for(int j=ql;j<=qr;j++)
		{
			if(qrList[j].r<L[i]) continue;
			if(qrList[j].l>R[i]) continue;
			long long val=0;
			if(qrList[j].l<L[i]) val+=lf[qrList[j].l];
			if(qrList[j].r>R[i]) val+=rf[qrList[j].r];
			tans[qrList[j].id]=max(tans[qrList[j].id],val);
		}
	}

	blkcnt=0;
	for(int i=nl;i<=nr;i+=m)
	{
		L[++blkcnt]=i;
		R[blkcnt]=min(i+m-1,nr);
	}
	for(int i=1;i<=blkcnt;i++)
	{
		lf[L[i]]=0;
		for(int j=L[i]-1;j>=nl;j--)
		{
			lf[j]=lf[j+1];
			if(j+m<=L[i]-1) lf[j]=max(lf[j],lf[j+m]+a[j]);
			else lf[j]=max(lf[j],a[j]);
		}
		rf[R[i]]=0;
		for(int j=R[i]+1;j<=nr;j++)
		{
			rf[j]=rf[j-1];
			if(j-m>=R[i]+1) rf[j]=max(rf[j],rf[j-m]+a[j]);
			else rf[j]=max(rf[j],a[j]);
		}
		for(int j=ql;j<=qr;j++)
		{
			if(qrList[j].r<L[i]) continue;
			if(qrList[j].l>R[i]) continue;
			long long val=0;
			if(qrList[j].l<L[i]) val+=lf[qrList[j].l];
			if(qrList[j].r>R[i]) val+=rf[qrList[j].r];
			tans[qrList[j].id]=max(tans[qrList[j].id],val);
		}
	}

	int latot=0,ratot=0;
	for(int i=1;i<=blkcnt;i++)
	{
		for(int j=L[i];j<=R[i];j++)
		{
			rval[j]=j-L[i]+1;
			if(rval[j]<=mid) la[++latot]=j;
			else ra[++ratot]=j;
		}
	}
	for(int i=1;i<=latot;i++) ta[nl+i-1]=la[i];
	for(int i=1;i<=ratot;i++) ta[nl+latot+i-1]=ra[i];
	for(int i=nl;i<=nr;i++) aid[ta[i]]=i;
	for(int i=nl;i<=nr;i++) ta[i]=a[ta[i]];
	for(int i=nl;i<=nr;i++) a[i]=ta[i];

	int lqrtot=0,rqrtot=0;
	for(int i=ql;i<=qr;i++)
	{
		if(rval[qrList[i].l]>rval[qrList[i].r]) continue;
		if(rval[qrList[i].r]<=mid)
		{
			lqrList[++lqrtot]=qrList[i];
			lqrList[lqrtot].l=aid[lqrList[lqrtot].l];
			lqrList[lqrtot].r=aid[lqrList[lqrtot].r];
		}
		if(rval[qrList[i].l]>mid)
		{
			rqrList[++rqrtot]=qrList[i];
			rqrList[rqrtot].l=aid[rqrList[rqrtot].l];
			rqrList[rqrtot].r=aid[rqrList[rqrtot].r];
		}
	}
	for(int i=1;i<=lqrtot;i++) qrList[ql+i-1]=lqrList[i];
	for(int i=1;i<=rqrtot;i++) qrList[ql+lqrtot+i-1]=rqrList[i];
	if(mid<=B) Solve1(nl,nl+latot-1,ql,ql+lqrtot-1,mid);
	else Solve2(nl,nl+latot-1,ql,ql+lqrtot-1,mid);
	if(m-mid<=B) Solve1(nl+latot,nl+latot+ratot-1,ql+lqrtot,ql+lqrtot+rqrtot-1,m-mid);
	else Solve2(nl+latot,nl+latot+ratot-1,ql+lqrtot,ql+lqrtot+rqrtot-1,m-mid);
}
int main()
{
	freopen("clear.in","r",stdin);
	freopen("clear.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)
	{
		long long v=max(a[i]-a[i+1],0ll);
		d[max(i-m+1,1)]-=v;
		d[i+1]+=v;
		gapS[i]=v+gapS[i-1];
	}
	for(int i=1;i<=n;i++) d[i]+=d[i-1];
	for(int i=1;i<=n;i++) a[i]+=d[i];
	for(int i=1;i<=q;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		ans[i]=gapS[r-1]-gapS[l-1]+a[r]-d[r];
		if(l<=r-m)
		{
			qrList[++qrtot]=Query(l,r-m,i);
			tag[i]=1;
		}
	}

	// Part0::solve();
	if(m<=B) Solve1(1,n,1,qrtot,m);
	else Solve2(1,n,1,qrtot,m);

	for(int i=1;i<=q;i++) if(tag[i]) ans[i]+=tans[i];
	for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
}
